In automatically switched networks, a connection is a concatenation of link connections and sub-network connections that enable the transport of data from a source to a destination. A connection path through the network is a sequence of nodes starting with a begin node and terminating at an end node (optionally, traversing at least one intermediate node). There are numerous methods for provisioning a connection path through a network, including both manual path provisioning and automated path provisioning. The three basic types of algorithms currently used for automatic path provisioning include hierarchical routing, step-by-step routing, and source routing, where source routing is essentially a hop-by-hop interaction between the nodes in the connection path.
In current source routed connection establishment algorithms, sequential setup is employed to establish connections across a network having a plurality of nodes. In source routed connection setup, when a connection is to be set up in a network, a connection request message is generated in a begin node and transmitted from the begin node to a first intermediate node in a sequence of nodes that will be traversed by the connection. The first intermediate node processes the connection request message received from the begin node and then forwards the connection request message to the next intermediate node in the sequence. This process continues until the final intermediate node in the sequence transmits the connection request message to the end node in the sequence.
As the connection request message follows the traversed intermediate nodes along the connection path between the begin node and the end node, specific actions are performed at each of the intermediate nodes and the end node that require a certain amount of processing time. Such actions include receiving the message, reading the message, allocating the bandwidth required by the connection path, and the like. After the connection has been established, there is typically a handshake between the end node and the begin node in which the success or failure of the connection establishment is communicated from the end node to the begin node.
Using this method of serial transmission and processing, the connection setup time is calculated as the sum of the transmission times required to transmit the connection request message from one node in the sequence to the next node in the sequence, and the processing time that each node in the sequence spends processing the connection request message. Therefore, in this method, and other serial methods of establishing connections across a network having a plurality of nodes, the connection setup time is a direct function of the connection path length (number of nodes in the sequence).
Unfortunately, as the size of communication networks continues to grow, the connection paths provisioned through a network tend to traverse increasing numbers of nodes, significantly increasing the time required to establish a connection path through the network. This situation is exacerbated by the fact that increases in the size of communication networks typically results in significant increases in the number of connection paths that are to be established through the networks. Therefore, a faster method of performing source routed connection path provisioning is desired.